// 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。

// 如果数组元素个数小于 2，则返回 0。

// 示例 1:

// 输入: [3,6,9,1]
// 输出: 3
// 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
// 示例 2:

// 输入: [10]
// 输出: 0
// 解释: 数组元素个数小于 2，因此返回 0。
// 说明:

// 你可以假设数组中所有元素都是非负整数，且数值在 32 位有符号整数范围内。
// 请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。

#include "stdc++.h"

// 先排序
// 不是线性时间
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n == 0 || n < 2) return 0;
        sort(nums.begin(), nums.end());
        int res{0};
        for (int i{0}; i < n-1; ++i) {
            res = max(res, nums[i+1] - nums[i]);
        }
        return res;
    }
};


// 桶排序
// 桶的大小是相同的
// 桶之间的间距也是固定的, 1
class Solution {
public:
    struct Bucket {
        bool used{false};
        int minVal{numeric_limits<int>::max()};
        int maxVal{numeric_limits<int>::min()};
    };
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n == 0 || n < 2) return 0;
        
        int min_num = *min_element(nums.begin(), nums.end()); // nums中最小值
        int max_num = *max_element(nums.begin(), nums.end()); // nums中最大值

        int bucketSize = max(1, (max_num - min_num) / (n - 1)); // bucket size or capacity
        int bucketNum = (max_num - min_num) / bucketSize + 1; // number of buckets
        vector<Bucket> buckets(bucketNum);

        for (auto& num : nums) {
            int bucketIdx = (num - min_num) /bucketSize; // locating correct bucket
            buckets[bucketIdx].used = true;
            buckets[bucketIdx].minVal = min(num, buckets[bucketIdx].minVal);
            buckets[bucketIdx].maxVal = max(num, buckets[bucketIdx].maxVal);
        }

        int preBucketMax = min_num;
        int res{0};
        for (auto& bucket : buckets) {
            if (!bucket.used) continue;
            res = max(res, bucket.minVal - preBucketMax); // 桶间距 = 当前桶的最小值 - 前一个桶的最大值
            preBucketMax = bucket.maxVal;
        }

        return res;
    }
};

/* 基数排序
O(n)时间内完成整数的排序
*/
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        int exp{1};
        vector<int> buf(n, 0);
        int maxVal = *max_element(nums.begin(), nums.end());
        while (maxVal >= exp) {
            vector<int> cnt(10, 0);
            for (int i{0}; i < n; ++i) {
                int digit = (nums[i]/ exp) % 10;
                ++cnt[digit];
            }
            for (int i{1}; i < 10; ++i) {
                cnt[i] += cnt[i - 1];
            }
            for (int i{n - 1}; i >= 0; --i) {
                int digit = (nums[i] / exp) % 10;
                buf[cnt[digit] - 1] = nums[i];
                --cnt[digit];
            }
            copy(buf.begin(), buf.end(), nums.begin());
            exp *= 10;
        }
        int res{0};
        for (int i{1}; i < n; ++i) {
            res = max(res, nums[i] - nums[i - 1]);
        }
        return res;
    }
};

/* 桶排序
*/
class Solution {
public:
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        int d = max(1, (maxVal - minVal) / (n - 1));
        int bucketSize = (maxVal - minVal) / d + 1;

        vector<pair<int, int>> bucket(bucketSize, {-1, -1}); // 存储 (桶内最小值，桶内最大值) 对，(-1, -1) 表示该桶是空的
        for (int i{0}; i < n; ++i) {
            int index = (nums[i] - minVal) / d;
            if (bucket[index].first == -1) {
                bucket[index].first = nums[i];
                bucket[index].second = nums[i];
            } else {
                bucket[index].first = min(bucket[index].first, nums[i]);
                bucket[index].second = max(bucket[index].second, nums[i]);
            }
        }

        int res{0};
        int pre{-1};
        for (int i{0}; i < bucketSize; ++i) {
            if (bucket[i].first == -1) continue;
            if (pre != -1) {
                res = max(res, bucket[i].first - bucket[pre].second);
            }
            pre = i;
        }
        return res;
    }
};